package com.intelli.eve.core.data_structure.priority_queue;

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Author: Sergey42
 * Date: 21.12.2014 15:51
 */
@SuppressWarnings("unchecked")
public abstract class AbstractPQ<T> implements PriorityQueue<T> {

    protected T[] pq;                    // store items at indices 1 to N
    protected int size;                  // number of items on priority queue
    protected Comparator<T> comparator;  // optional Comparator

    public AbstractPQ(int initCapacity) {
        pq = (T[]) new Object[initCapacity + 1];
        size = 0;
    }

    public AbstractPQ(int initCapacity, Comparator<T> comparator) {
        this.comparator = comparator;
        pq = (T[]) new Object[initCapacity + 1];
        size = 0;
    }

    public AbstractPQ(T[] keys) {
        size = keys.length;
        pq = (T[]) new Object[keys.length + 1];
        System.arraycopy(keys, 0, pq, 1, size);
        for (int k = size / 2; k >= 1; k--)
            sink(k);
        assert isNormalizedHeap();
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public T peekTop() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    @Override
    public void insert(T item) {
        if (size >= pq.length - 1) resize(2 * pq.length);
        // add item, and percolate it up to maintain heap invariant
        pq[++size] = item;
        swim(size);
        assert isNormalizedHeap();
    }

    // helper function to double the size of the heap array
    protected void resize(int capacity) {
        assert capacity > size;
        T[] temp = (T[]) new Object[capacity];
        System.arraycopy(pq, 1, temp, 1, size);
        pq = temp;
    }

    protected void exchange(int i, int j) {
        T swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }

    protected boolean greater(int i, int j) {
        if (comparator == null) return ((Comparable<T>) pq[i]).compareTo(pq[j]) > 0;
        else return comparator.compare(pq[i], pq[j]) > 0;
    }

    protected boolean less(int i, int j) {
        if (comparator == null) return ((Comparable<T>) pq[i]).compareTo(pq[j]) < 0;
        else return comparator.compare(pq[i], pq[j]) < 0;
    }

    protected void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exchange(k, k / 2);
            k = k / 2;
        }
    }

    protected void sink(int k) {
        while (2 * k <= size) {
            int j = 2 * k;
            if (j < size && isMore(j, j + 1)) j++;
            if (!isMore(k, j)) break;
            exchange(k, j);
            k = j;
        }
    }

    protected boolean isNormalizedHeap() {
        return isNormalizedHeap(1);
    }

    // is subtree of pq[1..size] rooted at k a min heap?
    protected boolean isNormalizedHeap(int k) {
        if (k > size) return true;
        int left = 2 * k, right = 2 * k + 1;
        if (left <= size && isMore(k, left)) return false;
        if (right <= size && isMore(k, right)) return false;
        return isNormalizedHeap(left) && isNormalizedHeap(right);
    }

    protected abstract boolean isMore(int i, int j);

    protected abstract AbstractPQ<T> newPQ(int size);

    public abstract T pollTop();

    @Override
    public Iterator<T> iterator() {
        return new HeapIterator();
    }

    protected class HeapIterator implements Iterator<T> {

        protected AbstractPQ<T> copy;

        // add all items to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            if (comparator == null) copy = newPQ(size());
            else copy = new MaxPQ<>(size(), comparator);
            for (int i = 1; i <= size; i++)
                copy.insert(pq[i]);
        }

        @Override
        public boolean hasNext() {
            return !copy.isEmpty();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public T next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.pollTop();
        }
    }
}
